package graph;

import java.util.*;

public class Graph {

	//存储 顶点 的集合
	private ArrayList<String> vertexList;
	//存储图对应的邻接矩阵
	private int[][] edges;
	//表示有多少条边
	private int numOfVertex;
	//记录某个顶点是否被访问过
	private boolean[] isVisited;

	public static void main(String[] args) {
		String vertexs[] = {"A", "B", "C", "D", "E", "F", "G"};
		int n = vertexs.length;
		Graph graph = new Graph(n);
		for (String value : vertexs) {
			graph.insertVertex(value);
		}
		graph.insertEdge(0, 3, 1);
		graph.insertEdge(0, 4, 1);
		graph.insertEdge(2, 3, 1);
		graph.insertEdge(1, 4, 1);
		graph.insertEdge(2, 5, 1);
		graph.insertEdge(1, 5, 1);
		graph.insertEdge(1, 6, 1);
		graph.insertEdge(3, 6, 1);

		graph.showGraph();

		graph.BFS2();
	}


	/**
	 * 构造器
	 *
	 * @param n 顶点个数
	 */
	public Graph(int n) {
		//初始化矩阵 和 vertextList
		edges = new int[n][n];
		vertexList = new ArrayList<>(n);
		numOfVertex = 0;
		isVisited = new boolean[n];
	}

	//=====深度优先============================

	/**
	 * 得到 当前节点 的第一个邻接节点的下标 （w）
	 *
	 * @param index 当前节点的下标
	 * @return 如果存在 就返回对应的下标，否则返回 -1
	 */
	public int getFirstNeighbor(int index) {
		for (int j = 0; j < vertexList.size(); j++) {
			if (edges[index][j] > 0) {
				//下一个邻接点存在
				return j;
			}
		}
		return -1;
	}

	/**
	 * 根据前一个邻接节点的下标，来获取下一个邻接节点
	 *
	 * @param v1
	 * @param v2
	 * @return
	 */
	public int getNextNeighbor(int v1, int v2) {
		for (int j = v2 + 1; j < vertexList.size(); j++) {
			if (edges[v1][j] > 0) {
				return j;
			}
		}
		return -1;
	}

	//对某一个节点进行深度优先遍历
	//i 第一次就是 0
	public void DFS(boolean[] isVisited, int index) {
		System.out.print(getVertexListByIndex(index) + " -> ");
		//把 该节点 置为 已访问过
		isVisited[index] = true;
		//查找 节点 index 的第一个邻接节点 w
		int w = getFirstNeighbor(index);

		while (w != -1) {//若w存在，则有邻接节点
			//判断是否被访问过
			if (!isVisited[w]) {
				//没有被访问
				DFS(isVisited, w);
			} else {
				//已经被访问
				w = getNextNeighbor(index, w);
			}

		}
	}

	//对 DFS方法 进行重载，遍历所有的节点并进行 DFS
	public void DFS() {
		//遍历所有的节点进行 DFS
		for (int i = 0; i < vertexList.size(); i++) {
			if (!isVisited[i]) {
				DFS(isVisited, i);
			}
		}
	}

	public void DFS2(boolean[] isVisited, int index) {
		System.out.print(getVertexListByIndex(index) + " -> ");
		isVisited[index] = true;
		for (int i = 0; i < vertexList.size(); i++) {
			if (!isVisited[i] && edges[index][i] > 0) {
				DFS2(isVisited, i);
			}
		}
	}

	public void DFS2() {
		DFS2(isVisited, 0);
	}
	//========================================

	//=====宽度优先============================
	//对一个节点进行宽度优先
	public void BFS(boolean[] isVisited, int index) {
		int u;//头节点对应的下标
		int w;//邻接节点的下标

		LinkedList<Integer> queue = new LinkedList<>();
		//访问节点
		System.out.print(getVertexListByIndex(index) + " -> ");
		isVisited[index] = true;
		queue.addLast(index);
		while (!queue.isEmpty()) {
			//取出队列的头节点下标
			u = queue.removeFirst();
			//得到第一个邻接节点的下标
			w = getFirstNeighbor(u);
			while (w != -1) {//是否存在
				//是否被访问过
				if (!isVisited[w]) {
					System.out.print(getVertexListByIndex(w) + " -> ");
					isVisited[w] = true;
					queue.addLast(w);
				} else {
					w = getNextNeighbor(u, w);
				}


			}
		}

	}

	public void BFS() {
		for (int i = 0; i < vertexList.size(); i++) {
			if (!isVisited[i]) {
				BFS(isVisited, i);
			}

		}
	}

	public void BFS2(boolean[] isVisited, int start) {

		Queue<Integer> q = new LinkedList<>();
		q.add(start); //将起始顶点加入队列


		while (!q.isEmpty()) {
			//取出队首元素
			int top = q.poll();
			System.out.print(getVertexListByIndex(top) + " -> ");
			isVisited[top] = true;

			//访问队首元素结点的邻接表
			for (int i = 0; i < vertexList.size(); i++) {
				//在该邻接表中，如果某元素还没被访问到，说明还未遍历，则访问这个结点
				if (edges[top][i] > 0 && !isVisited[i]) {
					isVisited[i] = true;
					q.add(i);
				}
			}
		}
	}

	public void BFS2() {
		BFS2(isVisited, 0);
	}


	//========================================

	//插入顶点
	public void insertVertex(String vertex) {
		vertexList.add(vertex);
	}

	/**
	 * 添加边
	 *
	 * @param v1     顶点 1 的下标
	 * @param v2     顶点 2 的下标
	 * @param weight 权值（无关联为 0 ，有关联为 1）
	 */
	public void insertEdge(int v1, int v2, int weight) {
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		numOfVertex++;
	}


	public ArrayList<String> getVertexList() {
		return vertexList;
	}

	//返回 第 i 个顶点
	public String getVertexListByIndex(int i) {
		return vertexList.get(i);
	}

	//顶点个数
	public int getVertexListSize() {
		return vertexList.size();
	}

	public int getnumOfVertex() {
		return numOfVertex;
	}

	//返回 v1 和 v2 的权值
	public int getWeigth(int v1, int v2) {
		return edges[v1][v2];
	}

	//显示 邻接矩阵
	public void showGraph() {
		for (int i = 0; i < vertexList.size(); i++) {
			System.out.println(Arrays.toString(edges[i]));
		}

	}

}
